class Solution {
    /**
        遍历每个数字 将每个数字作为树根 
        假设n=3 d[i] 表示序列长度为i的二叉搜索树的种树
            当1作为root: root1 = d[0]*d[2] (左子树0 右子树2)
            当2作为root: root2 = d[1]*d[1] (左子树1 右子树1)
            当3作为root: root3 = d[2]*d[0] (左子树2 右子树0)
     */
    public int numTrees(int n) {
        int[] d = new int[n+1];
        d[0] = d[1] = 1;

        for(int i=2; i<=n; i++){
            for(int j=0; j<=i-1; j++){
                d[i] += d[j]*d[i-j-1];
            }
        }
        return d[n];
    }
}